package myHashMap;

import java.util.ArrayList;
import java.util.List;

public class MyHashMap<K, V> {
	
	private static final float DEFAULT_LOAD_FACTOR = 0.75f;
	private static final int DEFAULT_CAPACITY = 128;
	private static final int MAX_CAPACITY = Integer.MAX_VALUE;
	
	public MyHashMap(int capacity, float loadFactor) {
		entries = new Entry[capacity];
		this.loadFactor = loadFactor;
		threshold = (int) (loadFactor*capacity);
		size = 0;
	}
	
	public MyHashMap(int capacity) {
		this(capacity, DEFAULT_LOAD_FACTOR);
	}
	
	public MyHashMap() {
		this(DEFAULT_CAPACITY, DEFAULT_LOAD_FACTOR);
	}
	
	public void put(K key, V value) {
		size++;
		if (size > threshold) {
			resize(entries.length*2);
		}
		int hash = hash(key.hashCode());
		int index = index(hash, entries.length);
		Entry<K, V> entry = entries[index];
		if (entry == null) {
			entry = new Entry<K, V>();
			entry.key = key;
			entry.value = value;
			entries[index] = entry;
		} else {
			Entry<K, V> newEntry = new Entry<K, V>();
			newEntry.key = key;
			newEntry.value = value;
			newEntry.next = entry;
			entries[index] = newEntry;
		}
	}
	
	V get(K key) {
		int hash = hash(key.hashCode());
		int index = index(hash, entries.length);
		Entry<K, V> entry = entries[index];
		if (entry == null) return null;
		if (entry.key.equals(key)) {
			return entry.value;
		} else {
			do {
				entry = entry.next;
				if (entry.key.equals(key)) {
					return entry.value;
				}
			} while (entry != null);
			return null;
		}
	}
	
	void remove(K key) {
		if (!iskey(key)) return;
		int hash = hash(key.hashCode());
		int index = index(hash, entries.length);
		Entry<K, V> entry = entries[index];
		if (entry.key.equals(key)) {
			entries[index] = entry.next;
			size--;
			return;
		} else {
			do {
				Entry<K, V> prevEntry = entry;
				entry = entry.next;
				if (entry.key.equals(key)) {
					prevEntry.next = entry.next;
					size--;
					return;
				}
			} while (entry != null);
		}
	}
	
	List<K> getKeys() {
		ArrayList<K> keys = new ArrayList<K>();
		for (Entry<K, V> entry: entries) {
			while (entry != null){
				keys.add(entry.key);
				entry = entry.next;
			}
		}
		return keys;
	}
	
	List<V> getValues() {
		ArrayList<V> values = new ArrayList<V>();
		for (Entry<K, V> entry: entries) {
			while (entry != null){
				values.add(entry.value);
				entry = entry.next;
			}
		}
		return values;
	}
	
	void change(K key, V value) {
		if (!iskey(key)) {
			put(key, value);
			return;
		} else {
			int hash = hash(key.hashCode());
			int index = index(hash, entries.length);
			Entry<K, V> entry = entries[index];
			if (entry.key.equals(key)) {
				entry.value = value;
				return;
			} else {
				do {
					entry = entry.next;
					if (entry.key.equals(key)) {
						entry.value = value;
						return;
					}
				} while (entry != null);
			}
		}
	}
	
	boolean iskey(K key) {
		return (!(get(key) == null));
	}
	
	int size() {
		return size;
	}
	
	private int hash(int key) {
		return key;
	}
	
	private int index(int hash, int length) {
		return hash & (length - 1);
	}
	
	private void resize(int newCapacity) {
		if (entries.length == MAX_CAPACITY) {
			threshold = Integer.MAX_VALUE;
			return;
		}
		Entry<K,V>[] newTable = new Entry[newCapacity];
		transfer(newTable);
		entries = newTable;
		threshold = (int) (newCapacity*loadFactor);
	}
	
	private void transfer(Entry<K,V>[] newTable) {
		for (Entry<K, V> entry: entries) {
			if (entry != null){
				int hash = hash(entry.key.hashCode());
				int index = index(hash, newTable.length);
				newTable[index] = entry;
			}
		}
	}
	
	private class Entry<K, V> {
		public K key;
		public V value;
		public Entry<K, V> next;
		
		public int hashCode() {
			return (key==null   ? 0 : key.hashCode()) ^ (value==null ? 0 : value.hashCode());
		}
	}
	
	private Entry<K, V>[] entries;
	private int size;
	private float loadFactor;
	private int threshold;
}
